package codingforgreat.class09;

public class Class03_LIS {
    public static int lengthOfLIS(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        if(arr.length == 1){
            return 1;
        }
        int[] dp = new int[arr.length];
        dp[0] = 1;
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = Math.max(dp[i], arr[i] > arr[j] ? dp[j] + 1 : 1);
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
    public static int lengthOfLIS1(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        if(arr.length == 1){
            return 1;
        }
        int[] dp = new int[arr.length];
        int[] end = new int[arr.length];
        end[0] = arr[0];
        int right = 0;
        int max = 1;
        for (int i = 1; i < arr.length; i++) {
            int l = 0;
            int r = right;
            // 在ends[l...r]范围上二分
            // 如果 当前数(arr[i]) > ends[m]，砍掉左侧
            // 如果 当前数(arr[i]) <= ends[m]，砍掉右侧
            // 整个二分就是在ends里寻找 >= 当前数(arr[i])的最左位置
            // 就是从while里面出来时，l所在的位置。
            // 如果ends中不存在 >= 当前数(arr[i])的情况，将返回有效区的越界位置
            // 也就是从while里面出来时，l所在的位置，是有效区的越界位置
            // 比如 : ends = { 3, 5, 9, 12, 再往右无效}
            // 如果当前数为8, 从while里面出来时，l将来到2位置
            // 比如 : ends = { 3, 5, 9, 12, 再往右无效}
            // 如果当前数为13, 从while里面出来时，l将来到有效区的越界位置，4位置
            while(l <= r){
                int mid = (l + r) / 2;
                if(arr[i] <= end[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
            right = Math.max(right, l);
            // l的位置，就是当前数应该填到ends数组里的位置
            end[l] = arr[i];
            // 更新全局变量
            max = Math.max(max, l + 1);
        }
        return max;
    }

}
